package com.gorkr;

import org.junit.jupiter.api.Test;

import java.lang.reflect.Array;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class L120 {

    public int minimumTotal(List<List<Integer>> triangle) {

        // dp[i][j]表示从dp[0][0]到dp[i][j]的最短路径和
        int n = triangle.size();
        int m = triangle.get(n-1).size();
        int[][] dp = new int[n][n];


        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                dp[i][j] = Integer.MAX_VALUE;
            }
        }
        dp[0][0] = triangle.get(0).get(0);

        for (int i = 1; i < n; i++) {
            dp[i][0] = dp[i-1][0]+ triangle.get(i).get(0);

        }

        for (int i =1; i<n; i++){
            for (int j =1; j<=i; j++){
                dp[i][j] = Math.min(dp[i-1][j-1], dp[i-1][j]) + triangle.get(i).get(j);

            }
        }

        int res = Integer.MAX_VALUE;
        for (int i = 0; i < n; i++) {
             res = Math.min(dp[n-1][i],res);

        }

        return res;
    }
    @Test
    public void test(){

        List<List<Integer>> triangle = new ArrayList<>();
        List<Integer> t1 = new ArrayList<>(); t1.add(2); triangle.add(t1);
        List<Integer> t2 = new ArrayList<>(); t2.add(3); t2.add(4); triangle.add(t2);
        List<Integer> t3 = new ArrayList<>(); t3.add(6); t3.add(5); t3.add(7); triangle.add(t3);

        System.out.println(        this.minimumTotal(triangle));


    }
}
